﻿#include <iostream>
#include "BinaryTree.h"

static int maxDepth(BinaryTreeNode* head)
{
    auto cur = head;
    int depth = 0;
    while (cur)
    {
        ++depth;
        cur = cur->left;
    }

    return depth;
}

static int minDepth(BinaryTreeNode* head)
{
    auto cur = head;
    int depth = 0;
    while (cur)
    {
        ++depth;
        cur = cur->right;
    }

    return depth;
}

static int fullTreeNodeCount(int depth)
{
    return (int)pow(2, depth) - 1;
}

static int recur(BinaryTreeNode* head, int headMaxDepth)
{
    if (!head) return 0;

    int total = 1;
    int rightMaxDepth = maxDepth(head->right);
    if (rightMaxDepth == headMaxDepth - 1)
    {
        // 左子树必定满
        total += fullTreeNodeCount(headMaxDepth - 1);
        total += recur(head->right, headMaxDepth - 1);
    }
    else
    {
        // 右子树必定满
        total += fullTreeNodeCount(headMaxDepth - 2);
        total += recur(head->left, headMaxDepth - 1);
    }

    return total;
}

// 求完全二叉树的节点个数
//
// 思路：
// 递归求解
// 1. 首先求出整棵树的深度，因为整棵树是完全二叉树，所以深度 = 最左子树的高度
// 2. 假设有一个节点，
// (1)它的右子树的高度已经到达整棵树的深度了，则它的左子树必定是满二叉树, 满二叉树可以根据公式求解总的节点数，/然/后递归求解右子树
// (2)它的右子树的高度没有到达整棵树的深度，则它的右子树也是满二叉树，只不过其高度不到整颗树的深度而已, 递归求解左子树
int main_NodeCountOfCompleteBinaryTree()
{
    auto head = new BinaryTreeNode(11);
    head->left = new BinaryTreeNode(7);
    head->right = new BinaryTreeNode(15);
    head->left->left = new BinaryTreeNode(3);
    head->left->left->left = new BinaryTreeNode(1);
    head->left->left->right = new BinaryTreeNode(4);
    head->left->right = new BinaryTreeNode(9);
    head->left->right->left = new BinaryTreeNode(8);
    head->left->right->right = new BinaryTreeNode(10);
    head->right->left = new BinaryTreeNode(13);
    head->right->left->left = new BinaryTreeNode(12);
    head->right->right = new BinaryTreeNode(18);
	
    int count = recur(head, maxDepth(head));
    printf("%d\n", count);

    deleteBinaryTree(head);
    return 0;
}